/**
 * @author wangj881
 * @date 2025-02-27 10:34
 */
public class L148_3 {

    public static void main(String[] args) {

    }

    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            // 先找中点
            ListNode slow = head;
            ListNode fast = head.next;

            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode middle = slow.next;
            slow.next = null;

            ListNode left = sortList(head);
            ListNode right = sortList(middle);

            // 拼接链表
            ListNode node = new ListNode();
            ListNode cur = node;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    cur.next = left;
                    left = left.next;
                } else {
                    cur.next = right;
                    right = right.next;
                }
                cur = cur.next;
            }
            cur.next = left == null ? right : left;
            return node.next;
        }
    }
}
